COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\input macro[1,mps]
C00009 ENDMK
C⊗;
\input macro[1,mps]
\magnification\magstephalf
\baselineskip 14pt
\leftline{\sevenrm A11.Tex[154,rwf]\today}
\leftline{\copyright\sevenrm Robert W. Floyd, February 3, 1989}
\leftline{\sevenrm Unpublished draft}
\bigskip
\noindent{\bf Regular Expressions for FALs}

An algorithm for reducing a FA (whether deterministic or not) to a
regular expression removes one intermediate vertex at a time from
the~FA, labelling the remaining arcs with regular expressions.
It is exemplified by changing

$$\vcenter{\baselineskip0pt\halign{$\ctr{#}\;$&$\ctr{#}$\q&$\ctr{#}$\q&$\ctr{#}$\q
&$\ctr{#}$\q&$\ctr{#}$\q&$\ctr{#}$\cr
&&&b\cr
\noalign{\bigskip}
&&a&&c\cr
\Longrightarrow&1&&2&&3\cr
\noalign{\bigskip}
&&&d\cr}}$$

\bigskip\noindent
to

$$\vcenter{\baselineskip0pt\halign{$\ctr{#}\;$&$\ctr{#}$\qq&$\ctr{#}$\qq
&$\ctr{#}$\cr
&&d+ab↑{\ast}c\cr
\Longrightarrow&1&&3\cr}}$$

\bigskip
\noindent If vertex $j$ is being removed, and if there is an arc from $i$ to~$j$
and one from $j$ to~$k$, new arcs are introduced. There are four
cases, depending on the existence of an arc from $i$ to~$k$, and
one from $j$ to~$j$.

$$\vcenter{\baselineskip0pt\halign{$\ctr{#}$\q&$\ctr{#}$\q
&$\ctr{#}$\q&$\ctr{#}$\q&$\ctr{#}$\qq\qq
&$\ctr{#}$\q&$\ctr{#}$\q&$\ctr{#}$\cr
&\multispan2\hbox{Old graph}&&&&\hbox{New graph}\cr
\noalign{\bigskip\bigskip}
&a&&b&&&ab\cr
i&&j&&k&i&&k\cr
\noalign{\bigskip\bigskip}
&&c\cr
\noalign{\bigskip}
&a&&b&&&ac↑{\ast}b\cr
i&&j&&k&i&&k\cr
\noalign{\bigskip\bigskip}
&a&&b&&&ab+d\cr
i&&j&&k&i&&k\cr
\noalign{\bigskip}
&&d\cr
\noalign{\bigskip\bigskip}
&&c\cr
\noalign{\bigskip}
&a&&b&&&ac↑{\ast}b+d\cr
i&&j&&k&i&&k\cr
\noalign{\bigskip}
&&d\cr}}$$

\vfill\eject

\noindent{Example:} Find a regular expression for the language of
this machine.

$$\vcenter{\halign{
$\ctr{#}$\q&$\ctr{#}$&$\ctr{#}$\q&$\ctr{#}$\q&$\ctr{#}$\cr
&\Longrightarrow&A\cr
\noalign{\bigskip}
1&1&&0&0\cr
\noalign{\bigskip}
&&1\cr
C&&&&B\cr
&&0\cr}}$$

\bigskip
\disleft 40pt:{Step 1:}:Unique out-only start state, in-only accepting state.

$$\vcenter{\halign{$\ctr{#}\;$&$\ctr{#}$\q&$\ctr{#}$\q
&$\ctr{#}$\q&$\ctr{#}$\q&$\ctr{#}$\q
&$\ctr{#}$\q&$\ctr{#}$\q&$\ctr{#}$\q
&$\ctr{#}$\q&$\ctr{#}$\q&$\ctr{#}$\cr
&&&&&&&C\cr
&&&&1&&&&&&\Lambda\cr
&&\Lambda&&&1&&&&\phantom{1}\cr
\Longrightarrow&D&&A&&&1&&0&&&E\cr
&&&&&0&&&&\phantom{0}\cr
&&&&0&&&&&&\Lambda\cr
&&&&&&&B\cr}}$$

\bigskip
\disleft 40pt:{Step 2:}:Eliminate one intermediate node at a time.

\smallskip
\disleft 40pt:(2A):Eliminate $A$.

$$\vcenter{\halign{$\ctr{#}\;$&$\ctr{#}$\q&$\ctr{#}$\q
&$\ctr{#}$\q&$\ctr{#}$\q&$\ctr{#}$\q
&$\ctr{#}$\q&$\ctr{#}$\cr
&&&&00\cr
\noalign{\bigskip}
&&&&B\cr
&&0&&&&\Lambda\cr
\noalign{\bigskip}
\Longrightarrow&D&&0+10&&1+01&&E\cr
\noalign{\bigskip}
&&1&&&&\Lambda\cr
&&&&C\cr
\noalign{\bigskip}
&&&&11\cr}}$$

\bigskip
\disleft 40pt:(2B):Eliminate $B$.

$$\vcenter{\baselineskip0pt\halign{$\ctr{#}\;$&$\ctr{#}$\q&$\ctr{#}$
&$\ctr{#}$&$\ctr{#}$\q&$\ctr{#}$\cr
&&&0(00)↑{\ast}\cr
\noalign{\bigskip\bigskip}
&&1+0(00)↑{\ast}(1+01)&&\Lambda +(0+10)(00)↑{\ast}\cr
\Longrightarrow&D&&C&&E\cr
\noalign{\bigskip\bigskip\bigskip}
&&&11+(0+10)(00)↑{\ast}(1+01)\cr}}$$

\bigskip\noindent
and simplify 
$$\eqalign{1+0(00)↑{\ast}(1+01)&\q\hbox{to}\q 0↑{\ast}1\cr
11+(0+10)(00)↑{\ast}(1+01)&\q\hbox{to}\q (1+0)0↑{\ast}1\cr}$$

\bigskip\bigskip
$$\vcenter{\baselineskip0pt\halign{$\ctr{#}\;$&$\ctr{#}$\qq\qq&$\ctr{#}$\qq\qq
&$\ctr{#}$\q&$\ctr{#}$\q&$\ctr{#}$\cr
&&&0(00)↑{\ast}\cr
\noalign{\bigskip\bigskip}
&&0↑{\ast}1&&\Lambda +(0+10)(00)↑{\ast}\cr
\Longrightarrow&D&&C&&E\cr
\noalign{\bigskip\bigskip\bigskip}
&&&(1+0)0↑{\ast}1\cr}}$$

\bigskip
\disleft 30pt:(2C):Eliminate $C$.

$$\vcenter{\baselineskip0pt\halign{$\ctr{#}\;$&$\ctr{#}\q$&$\ctr{#}$\qq&$\ctr{#}$\cr
&&0(00)↑{\ast}+0↑{\ast}1\bigl((1+0)0↑{\ast}1\bigr)↑{\ast}\bigl(\Lambda 
+(0+10)(00)↑{\ast}\bigr)\cr
\Longrightarrow&D&&E\cr}}$$

\bigskip\noindent
and simplify the resulting regular expression (if you can).

\vfill\eject\end